# -*- coding: utf-8 -*-



import sys
import math

def maxheapify (A, i):
    ''' 
    Algoritmo de ordenacao Heapsort 
    Parametros de entrada 
        A -> Array para odernação 

    '''
    global heapzise
    
    l = 2*i
    r = 2*i + 1

    if l <= heapsize and A[l] > A[i] :
        largest = l
    else:
        largest = i
        pass

    if r <= heapsize and A[r] > A[largest] :
        largest = r
        pass
    
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxheapify(A, largest)
    pass
pass

def build_max_heap(A):
    for i in range(int(math.floor(len(A)/2)), 0, -1):
        maxheapify(A,i)
    pass
pass

def heapsort(A):
    global heapsize
    heapsize = len(A)-1
    build_max_heap(A)
    for i in range(len(A)-1, 1, -1):
        A[1], A[i] = A[i], A[1]
        heapsize = heapsize - 1
        maxheapify(A,1)
    pass
pass